#include<vector>
#include<unordered_set>
using namespace std;

class Solution {
private:
    struct Node {
        vector<Node*>childs;
        Node():childs(2,NULL){}
    };


public:
    int findMaximumXOR(vector<int>& nums) {
        Node* root = new Node();
        int res = 0;
        for (auto num : nums) {
            int cur = 0;
            Node* node = root;
            Node* prev = root;
            for (int i = 30; i >= 0; --i) {
                bool flag = (num & (1 << i)) >> i;
                if (node->childs[flag] == NULL) 
                    node->childs[flag] = new Node();
                node = node->childs[flag];
                if (prev == NULL) {
                    cur = 0;
                    continue;
                } 
                if (prev->childs[!flag] == NULL) 
                    prev = prev->childs[flag];
                else {
                    cur = cur | (1 << i);
                    prev = prev->childs[!flag];
                }
            }
            if (cur > res) res = cur;
        }
        return res;
    }
};


//class Solution {
//public:
//    int findMaximumXOR(vector<int>& nums) {
//        int res = 0;
//        int mask = 0;
//        for (int i = 30; i >= 0; --i) {
//            mask = mask | (1 << i);
//            unordered_set<int>set;
//            for (auto& num : nums)
//                set.insert(num & mask);
//            int tmp = res | (1 << i);
//            for (auto prefix : set) {
//                if (set.find(prefix ^ tmp) != set.end()) {
//                    res = tmp;
//                    break;
//                }
//            }
//        }
//        return res;
//    }
//};